/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-08-29
 * Time: 22:37
 */
public class Sort {

    //直接选择排序_实现方式1
    public static void chooseSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    //交换位置
    private static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //直接选择排序_实现方式2
    public static void chooseSort1(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(arr,left,minIndex);
            if (left == maxIndex) {
                maxIndex = minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }

    //堆排序
    public static void heapSort(int[] arr) {
        createHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }
    }
    //创建堆
    private static void createHeap(int[] arr) {
        for (int parent = (arr.length - 1 - 1)/2; parent >= 0; parent--) {
            siftDown(arr,parent,arr.length - 1);
        }
    }
    private static void siftDown(int[] arr,int parent,int size) {
        int child = 2*parent + 1;
        while (child <= size) {
            if (child + 1 <= size && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[parent] < arr[child]) {
                swap(arr, child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

}
